/*
 * @lc app=leetcode.cn id=106 lang=cpp
 *
 * [106] 从中序与后序遍历序列构造二叉树
 */
#include <unordered_map>
#include <vector>
using std::vector;
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution
{
  private:
    /* 记录一个值在中序序列中的index */
    std::unordered_map<int, int> val_to_index;
    /* 记录一个节点是否已经分配空间 */
    std::unordered_map<int, TreeNode *> val_to_node;
    TreeNode *build_helper(vector<int> &inorder, vector<int> &postorder, int post_right, int in_left, int in_right)
    {
        if (post_right < 0 || in_left > in_right) {
            return nullptr;
        }

        int root_val = postorder[post_right];
        TreeNode *root = nullptr;

        /* 拿到根节点，根节点没有创建的话，将其创建之后添加进hash表 */
        if (!val_to_node.count(root_val)) {
            val_to_node[root_val] = new TreeNode(root_val);
        }
        root = val_to_node[root_val];

        int root_inorder_index = val_to_index[root_val];
        int left_subtree_size = root_inorder_index - in_left;
        int right_subtree_size = in_right - root_inorder_index;

        /* 注意，后续遍历的顺序是：左右根，因此左子树的根节点所在的位置应该是 post_right - 1 - right_subtree_size */
        root->left = build_helper(inorder, postorder, post_right - 1 - right_subtree_size, in_left, root_inorder_index - 1);
        root->right = build_helper(inorder, postorder, post_right - 1, root_inorder_index + 1, in_right);

        return root;
    }

  public:
    TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder)
    {
        for (int i = 0; i < postorder.size(); i++) {
            val_to_index[inorder[i]] = i;
        }

        return build_helper(inorder, postorder, postorder.size() - 1, 0, inorder.size() - 1);
    }
};
// @lc code=end
